<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            一道LeetCode引发的惨案 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">一道LeetCode引发的惨案</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2018-10-31 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%90%9C%E7%B4%A2/">搜索</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>1.8k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>8 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="一道LeetCode搜索题引发的惨案"><a href="#一道LeetCode搜索题引发的惨案" class="headerlink" title="一道LeetCode搜索题引发的惨案"></a>一道LeetCode搜索题引发的惨案</h2><h3 id="1-先上-题目"><a href="#1-先上-题目" class="headerlink" title="1.先上 题目"></a>1.先上 <a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/word-ladder/" >题目<i class="fas fa-external-link-alt"></i></a></h3><p>给定两个单词（<em>beginWord _和 _endWord_）和一个字典，找到从 _beginWord</em> 到 <em>endWord</em> 的最短转换序列的长度。转换需遵循如下规则：</p>
<ol>
<li> 每次转换只能改变一个字母。</li>
<li>转换过程中的中间单词必须是字典中的单词。<br><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/word-ladder/" >原题链接<i class="fas fa-external-link-alt"></i></a><br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://imlgwpicture.oss-cn-qingdao.aliyuncs.com/blogImage/3V6EQ77R_%28%292SCR%248R%5B%245F7.png"
                      alt="oss"
                >其实这题明显是BFS(广搜) 题目类型也说了是广搜，但是我不信邪写了DFS(毕竟代码比较好写)，然后惨案就发生了。</li>
</ol>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">  <span class="comment">// 标记数组</span></span><br><span class="line"><span class="comment">// 默认都是0</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span>[] mark;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">ladderLength</span><span class="params">(String beginWord, String endWord, List&lt;String&gt; wordList)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 不存在</span></span><br><span class="line">	mark = <span class="keyword">new</span> <span class="keyword">int</span>[wordList.size() + <span class="number">1</span>];</span><br><span class="line">	<span class="keyword">if</span> (!wordList.contains(endWord)) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// dfs开始</span></span><br><span class="line">	dfs(beginWord, endWord, wordList);</span><br><span class="line">	<span class="comment">// 无法转换</span></span><br><span class="line">	<span class="keyword">if</span> (min == Integer.MAX_VALUE) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> min + <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> min = Integer.MAX_VALUE;</span><br><span class="line"></span><br><span class="line"><span class="comment">// dfs</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfs</span><span class="params">(String beginWord, String endWord, List&lt;String&gt; wordList)</span> </span>&#123;</span><br><span class="line">	<span class="comment">//当相等的时候</span></span><br><span class="line">	<span class="keyword">if</span> (beginWord.equals(endWord)) &#123;</span><br><span class="line">		<span class="keyword">int</span> step = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; mark.length; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span> (mark[i] == <span class="number">1</span>) &#123;</span><br><span class="line">				step++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//更新最小值</span></span><br><span class="line">		min = step &lt; min ? step : min;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; wordList.size(); i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (mark[i] == <span class="number">0</span> &amp;&amp; cmp(beginWord, wordList.get(i))) &#123;</span><br><span class="line">			mark[i] = <span class="number">1</span>;</span><br><span class="line">			dfs(wordList.get(i), endWord, wordList);</span><br><span class="line">			mark[i] = <span class="number">0</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 写一个函数判段是否只变化了一个字母</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">cmp</span><span class="params">(String s1, String s2)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> count = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s1.length(); i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (s1.charAt(i) != s2.charAt(i)) &#123;</span><br><span class="line">			count++;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> count == <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>结果直接TLE了，后来想了想DFS每次都会<strong>尝试</strong>所有情况，而给的例子后面的数据量也比较大，而且这题是要统计最短路径，要全部递归完才能确定最小值，我把数据拿来自己测试跑了好长时间都没跑出来，而BFS没有递归只是会耗费的空间会比较大。从这里也可以总结出来DFS跟适合判断是否存在是否可达之类的问题，BFS更适合做找最短最小之类的问题。上BFS代码</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">// 标记数组</span></span><br><span class="line">	<span class="comment">// 默认都是0</span></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span>[] mark;</span><br><span class="line">	<span class="comment">// 模拟队列</span></span><br><span class="line">	<span class="class"><span class="keyword">class</span> <span class="title">Que</span> </span>&#123;</span><br><span class="line">		String word;</span><br><span class="line">		<span class="keyword">int</span> step;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//BFS</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">ladderLengthBFS</span><span class="params">(String beginWord, String endWord, List&lt;String&gt; wordList)</span></span>&#123;</span><br><span class="line">        <span class="comment">// 不存在</span></span><br><span class="line">		mark = <span class="keyword">new</span> <span class="keyword">int</span>[wordList.size() + <span class="number">1</span>];</span><br><span class="line">		<span class="keyword">if</span> (!wordList.contains(endWord)) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// BFS</span></span><br><span class="line">		<span class="keyword">int</span> head = <span class="number">0</span>, tail = <span class="number">0</span>;</span><br><span class="line">		<span class="comment">// 初始化队列</span></span><br><span class="line">		Que[] que = <span class="keyword">new</span> Que[wordList.size() + <span class="number">1</span>];</span><br><span class="line">		<span class="comment">// 循环促使话述祖</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; que.length; i++) &#123;</span><br><span class="line">			que[i] = <span class="keyword">new</span> Que();</span><br><span class="line">		&#125;</span><br><span class="line">		que[tail].word = beginWord;</span><br><span class="line">		que[tail].word = beginWord;</span><br><span class="line">		que[tail].step = <span class="number">1</span>;</span><br><span class="line">		tail++;</span><br><span class="line">		<span class="keyword">int</span> flag=<span class="number">0</span>;</span><br><span class="line">		<span class="keyword">while</span> (head &lt; tail) &#123;</span><br><span class="line">			<span class="comment">// 遍历字典</span></span><br><span class="line">			<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; wordList.size(); i++) &#123;</span><br><span class="line">				<span class="keyword">if</span> (mark[i] == <span class="number">0</span> &amp;&amp; cmp(wordList.get(i), que[head].word)) &#123;</span><br><span class="line">					que[tail].word = wordList.get(i);</span><br><span class="line">					<span class="comment">//这里是从head开始的，所以应该是head的步数+1</span></span><br><span class="line">					que[tail].step=que[head].step+<span class="number">1</span>;</span><br><span class="line">					<span class="comment">// 标记为已经走过</span></span><br><span class="line">					mark[i] = <span class="number">1</span>;</span><br><span class="line">				   <span class="keyword">if</span> (que[tail].word.equals(endWord)) &#123;</span><br><span class="line">					<span class="comment">//到这里说明已经到终点了，而且是最短的，之后的最多就是相等</span></span><br><span class="line">					<span class="comment">//跳出循环</span></span><br><span class="line">                       flag=<span class="number">1</span>;</span><br><span class="line">                       <span class="keyword">break</span>;</span><br><span class="line">			    	&#125;</span><br><span class="line">                    tail++;</span><br><span class="line">				&#125;</span><br><span class="line">				</span><br><span class="line">			&#125;</span><br><span class="line">            <span class="keyword">if</span>(flag==<span class="number">1</span>)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">			<span class="comment">// 每次检查完一个单词就将其出队列</span></span><br><span class="line">			head++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> que[tail].step;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 写一个函数判段没吃是否只变化了一个字母</span></span><br><span class="line">	<span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">cmp</span><span class="params">(String s1, String s2)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">int</span> count = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s1.length(); i++) &#123;</span><br><span class="line">			<span class="keyword">if</span> (s1.charAt(i) != s2.charAt(i)) &#123;</span><br><span class="line">				count++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> count == <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br></pre></td></tr></table></figure>

<p>PS：刚刚修改了下代码，我也佩服自己BFS都还没搞清楚就直接上了代码，然后结果居然还是对的，之前在if判断队尾元素是不是和endWord相等后还维护了一个最小值min，后来想了想不对，最后一个和endWord相等的元素已经进栈了，已经是最短的了，后面的即使可以转换到也最多只能和当前的相等了。 如果只是为了统计最小值就可以直接break了。那如果不仅仅要统计最小值还要记录路径要怎么搞？</p>
<h3 id="2-加强版-单词接龙-2"><a href="#2-加强版-单词接龙-2" class="headerlink" title="2. 加强版 单词接龙 2"></a>2. <a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/word-ladder-ii/" >加强版<i class="fas fa-external-link-alt"></i></a> 单词接龙 2</h3><p>是一道困难等级的题，需要在上面的基础上找出所有的最短的路径。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">// 内部类</span></span><br><span class="line">	<span class="class"><span class="keyword">class</span> <span class="title">Que</span> </span>&#123;</span><br><span class="line">		String word;</span><br><span class="line">		<span class="keyword">int</span> step;</span><br><span class="line">		Que prev;</span><br><span class="line">		<span class="function"><span class="keyword">public</span> String <span class="title">toString</span><span class="params">()</span></span>&#123;</span><br><span class="line">			<span class="keyword">return</span> (word + <span class="string">&quot;:&quot;</span> + step);</span><br><span class="line">		&#125;		 </span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">//返回值</span></span><br><span class="line">	<span class="keyword">private</span>  List&lt;List&lt;String&gt;&gt; res=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line"></span><br><span class="line">	</span><br><span class="line">	<span class="comment">//BFS</span></span><br><span class="line">	<span class="keyword">public</span> List&lt;List&lt;String&gt;&gt; ladderLengthBFS(String beginWord, String endWord, List&lt;String&gt; wordList)&#123;</span><br><span class="line">        <span class="comment">//返回值</span></span><br><span class="line">		<span class="comment">//List&lt;List&lt;String&gt;&gt; res=new ArrayList&lt;&gt;();</span></span><br><span class="line">		</span><br><span class="line">        <span class="comment">// 不存在</span></span><br><span class="line">		mark = <span class="keyword">new</span> <span class="keyword">int</span>[wordList.size() + <span class="number">1</span>];</span><br><span class="line">		<span class="keyword">if</span> (!wordList.contains(endWord)) &#123;</span><br><span class="line">			<span class="keyword">return</span> res;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// BFS</span></span><br><span class="line">		<span class="keyword">int</span> head = <span class="number">0</span>, tail = <span class="number">0</span>;</span><br><span class="line">		<span class="comment">// 初始化队列</span></span><br><span class="line">		Que[] que = <span class="keyword">new</span> Que[wordList.size() + <span class="number">1</span>];</span><br><span class="line">		<span class="comment">// 循环促使话述祖</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; que.length; i++) &#123;</span><br><span class="line">			que[i] = <span class="keyword">new</span> Que();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//先把第一个单词放进去</span></span><br><span class="line">		que[tail].word = beginWord;</span><br><span class="line">		que[tail].word = beginWord;</span><br><span class="line">		que[tail].step = <span class="number">1</span>;</span><br><span class="line">		tail++;</span><br><span class="line">		List&lt;Que&gt; quelist=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">		<span class="keyword">while</span> (head &lt; tail) &#123;</span><br><span class="line">			<span class="comment">// 遍历字典</span></span><br><span class="line">			<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; wordList.size(); i++) &#123;</span><br><span class="line">				<span class="keyword">if</span> (mark[i] == <span class="number">0</span> &amp;&amp; cmp(wordList.get(i), que[head].word)) &#123;</span><br><span class="line">					que[tail].word = wordList.get(i);</span><br><span class="line">					<span class="comment">//这里是从head开始的，所以应该是head的步数+1</span></span><br><span class="line">					que[tail].step=que[head].step+<span class="number">1</span>;</span><br><span class="line">					<span class="comment">//que[head].next=que[tail];</span></span><br><span class="line">					<span class="comment">// 标记为已经走过</span></span><br><span class="line">					mark[i] = <span class="number">1</span>;</span><br><span class="line">				   <span class="keyword">if</span> (que[tail].word.equals(endWord)) &#123;	</span><br><span class="line">				   		<span class="comment">//记录最小值</span></span><br><span class="line">				   		min=que[tail].step;</span><br><span class="line">				   		<span class="comment">//到这里队列后面就不用再插入元素了</span></span><br><span class="line"></span><br><span class="line">				   		<span class="comment">//2.把之前走过的路在下一个head</span></span><br><span class="line"></span><br><span class="line">				   		<span class="comment">//将队列变成list</span></span><br><span class="line">				   		<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;=tail;j++)&#123;</span><br><span class="line">				   			quelist.add(que[j]);</span><br><span class="line">				   		&#125;</span><br><span class="line">				   		markDfs= <span class="keyword">new</span> <span class="keyword">int</span>[wordList.size() + <span class="number">1</span>]; </span><br><span class="line">				   		<span class="comment">// 1. 用DFS试一下</span></span><br><span class="line">				   		dfsBfs(que[<span class="number">0</span>],endWord,quelist);</span><br><span class="line">			    	&#125;</span><br><span class="line">                    tail++;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="comment">// 每次检查完一个单词就将其出队列</span></span><br><span class="line">			head++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">dfsBfs</span><span class="params">(Que beginWord,String endWord,List&lt;Que&gt; ques)</span></span>&#123;</span><br><span class="line">    	<span class="keyword">int</span> step = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; markDfs.length; i++) &#123;</span><br><span class="line">				<span class="keyword">if</span> (markDfs[i] == <span class="number">1</span>) &#123;</span><br><span class="line">					step++;</span><br><span class="line">				&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(step&gt;=min) <span class="keyword">return</span>;</span><br><span class="line">		<span class="keyword">if</span>(step+<span class="number">1</span>==min&amp;&amp;endWord.equals(beginWord.word))&#123;</span><br><span class="line">			List&lt;String&gt; list=<span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">			Stack&lt;String&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">			System.out.println(beginWord.word+<span class="string">&quot;:&quot;</span>+step);</span><br><span class="line">			Que temp=beginWord;</span><br><span class="line">				<span class="comment">//找到一条</span></span><br><span class="line">				<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;min;i++)&#123;</span><br><span class="line">					stack.push(temp.word);</span><br><span class="line">					System.out.print(temp.word+<span class="string">&quot;&lt;--&quot;</span>);</span><br><span class="line">					temp=temp.prev;</span><br><span class="line">				&#125;</span><br><span class="line">				System.out.println();</span><br><span class="line">				<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;min;i++)&#123;</span><br><span class="line">					list.add(stack.pop());</span><br><span class="line">				&#125;</span><br><span class="line">				res.add(list);</span><br><span class="line">				System.out.println(res);</span><br><span class="line">			<span class="keyword">return</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; ques.size(); i++) &#123;</span><br><span class="line">			<span class="keyword">if</span> (markDfs[i] == <span class="number">0</span> &amp;&amp; cmp(beginWord.word,ques.get(i).word))&#123;</span><br><span class="line">				markDfs[i] = <span class="number">1</span>;</span><br><span class="line">				<span class="comment">//连接两个节点</span></span><br><span class="line">				<span class="comment">//beginWord.next=ques.get(i);</span></span><br><span class="line">				ques.get(i).prev=beginWord;</span><br><span class="line">				dfsBfs(ques.get(i), endWord, ques);</span><br><span class="line">				markDfs[i] = <span class="number">0</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// private int step = 0;</span></span><br><span class="line">	<span class="keyword">int</span> min = Integer.MAX_VALUE;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 写一个函数判段没吃是否只变化了一个字母</span></span><br><span class="line">	<span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">cmp</span><span class="params">(String s1, String s2)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">int</span> count = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s1.length(); i++) &#123;</span><br><span class="line">			<span class="keyword">if</span> (s1.charAt(i) != s2.charAt(i)) &#123;</span><br><span class="line">				count++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> count == <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br></pre></td></tr></table></figure>
<p>整体上在Que上增加了一个prev的指针，遍历路径，一开始是用的BFS不过我想的太简单了，我只是把最后一个节点出队列然后再BFS，后来发现不行(居然还跑过了24个测试案例)，实际上这题我还是没有做出来，但是上面的方法应该是没问题的就是会TLE😭，大概思路就是先BFS缩短DFS需要遍历的字典然后控制每次递归的身体不能超过BFS的到的最短路径<br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://imlgwpicture.oss-cn-qingdao.aliyuncs.com/blogImage/blog.PNG"
                      alt="img9"
                >一开始只能跑几个数据的，优化下能跑几十个的，但是还是太慢了，毕竟是一道难题等以后学了相关的东西再来试试看能不能做出来吧.</p>
<hr>
<p>算法，学着挺有意思，就是头有点凉。</p>

        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：一道LeetCode引发的惨案</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2018-10-31 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2018/10/31/96e09a6a/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2018/11/17/65571397/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">CAS单点登陆系统Demo</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2018/10/05/8e2bbf7a/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">你有FreeBug么? ---&gt;Spring-solr</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2018/10/31/96e09a6a/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%B8%80%E9%81%93LeetCode%E6%90%9C%E7%B4%A2%E9%A2%98%E5%BC%95%E5%8F%91%E7%9A%84%E6%83%A8%E6%A1%88"><span class="nav-number">1.</span> <span class="nav-text">一道LeetCode搜索题引发的惨案</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#1-%E5%85%88%E4%B8%8A-%E9%A2%98%E7%9B%AE"><span class="nav-number">1.1.</span> <span class="nav-text">1.先上 题目</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2-%E5%8A%A0%E5%BC%BA%E7%89%88-%E5%8D%95%E8%AF%8D%E6%8E%A5%E9%BE%99-2"><span class="nav-number">1.2.</span> <span class="nav-text">2. 加强版 单词接龙 2</span></a></li></ol></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
